class Solution {
    /**
     * Finds the minimum element in a rotated sorted array.
     *
     * Given a rotated sorted array, find and return its minimum element.
     * The array was originally sorted in ascending order and rotated 1 to n times.
     * Time complexity must be O(log n).
     *
     * @param nums The rotated sorted array.
     * @return The minimum element in the array.
     */
    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;

        // Binary Search loop: keep searching while left is strictly less than right
        while (left < right) {
            int mid = (left + right) / 2; // Calculate the middle index

            // Check the slope to narrow down the search range
            if (nums[mid] > nums[right]) {
                // Uphill climb! Minimum is in the right half (excluding mid, starting from mid + 1)
                left = mid + 1;
            } else {
                // Downhill or valley! Minimum could be at mid or in the left half (including mid)
                right = mid; // Keep 'mid' in the search range, careful step!
            }
        }

        // Loop ends when left == right, and nums[left] (or nums[right]) is the minimum
        return nums[left];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        // Example 1
        int[] nums1 = {3, 4, 5, 1, 2};
        int min1 = solution.findMin(nums1);
        System.out.println("Example 1: Input nums = [3,4,5,1,2], Minimum = " + min1); // Output: 1

        // Example 2
        int[] nums2 = {4, 5, 6, 7, 0, 1, 2};
        int min2 = solution.findMin(nums2);
        System.out.println("Example 2: Input nums = [4,5,6,7,0,1,2], Minimum = " + min2); // Output: 0

        // Example 3
        int[] nums3 = {11, 13, 15, 17};
        int min3 = solution.findMin(nums3);
        System.out.println("Example 3: Input nums = [11,13,15,17], Minimum = " + min3); // Output: 11
    }
}